package com.future;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:139. ���ʲ��
 * ����һ���ַ��� s ��һ���ַ����б� wordDict ��Ϊ�ֵ䡣�����ж��Ƿ���������ֵ��г��ֵĵ���ƴ�ӳ� s ��
 * <p>
 * ע�⣺��Ҫ���ֵ��г��ֵĵ���ȫ����ʹ�ã������ֵ��еĵ��ʿ����ظ�ʹ�á�
 * <p>
 * ʾ�� 1��
 * <p>
 * ����: s = "leetcode", wordDict = ["leet", "code"]
 * ���: true
 * ����: ���� true ��Ϊ "leetcode" ������ "leet" �� "code" ƴ�ӳɡ�
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/word-break
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/16 10:26
 */
public class Solution_139 {

    public static void main(String[] args) {
        String s1 = "aaabb";
        String aaa = s1.substring(0, "aaa".length());
        System.out.println(aaa);
        String s = "leetcode";
        List<String> wordict = new ArrayList<String>() {{
            add("leet");
            add("code");
        }};
       /* s = "aaaaaaa";
        wordict.clear();
        wordict.add("aaaa");
        wordict.add("aaa");*/
        System.out.println(wordBreak(s, wordict));
    }

    /**
     * eg:
     * s = leetcode,wordDict={"leet","code"}
     * ����s
     * i=1,��s[0..1]�Ƿ�����ַ�������worDict��s[0..1]={"l"}
     * i=2,��s[0..2]�Ƿ�����ַ�������worDict��s[0..2]={"e","le"}
     * i=3,��s[0..3]�Ƿ�����ַ�������worDict��s[0..3]={"e","ee","lee"}
     * i=4,��s[0..4]�Ƿ�����ַ�������worDict��s[0..4]={"t","et","eet","leet"}������,dp={t,f,f,f,t}
     * i=5,��s[0..5]�Ƿ�����ַ�������worDict��s[0..5]={"leetc","eetc","etc","tc","c"}��������,dp={t,f,f,f,t,f}
     * i=6,��s[0..6]�Ƿ�����ַ�������worDict��s[0..6]={"leetco","eetco","etco","tco","co","o"}��������,dp={t,f,f,f,t,f,f}
     * i=7,��s[0..7]�Ƿ�����ַ�������worDict��s[0..7]={"leetcod","eetcod","etcod","tcod","cod","od","d"}��������,dp={t,f,f,f,t,f,f,f}
     * i=8,��s[0..8]�Ƿ�����ַ�������worDict��s[0..8]={"leetcode","eetcode","etcode","tcode","code","ode","de","e"}�����ڲ�����,dp={t,f,f,f,t,f,f,f,t}
     *
     * @param s
     * @param wordDict
     * @return
     */
    public static boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            //System.out.println("-----------i=" + i);  // ���Կ�����
            for (int j = 0; j < i; j++) {
                String val = s.substring(j, i);
                //System.out.print("str=" + val + "  ");//���Կ�����
                if (dp[j] && wordDict.contains(val)) {
                    dp[i] = true;
                    break;
                }
            }
            System.out.println();
        }
        return dp[s.length()];
    }
}
